1. Field of the Invention
The invention relates to a memory provided with retrieval features. Specifically, the invention refers to a content addressable memory (CAM) and a network frame switch which is located in a communication network and is used to switch network frames transferred via the communication network.
2. Description of Related Art
Conventionally, content addressable memories have been proposed that store data in a plurality of word memories before retrieval data is input. The conventional CAM retrieves one of the word memories which contains a bit pattern that matches or "hits" the bit pattern of all or a prescribed portion of the input retrieval data.
FIG. 3 is a circuit block diagram of a conventional CAM 10. The CAM 10 has a vertical array of word memories 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n, each of which has m bits of horizontal memory cells. In addition, the CAM 10 has a retrieval data register 12 which receives and latches one word of retrieval data. The CAM 10 also has a mask data register 13 which latches mask data (data that defines a portion of data valid for retrieval) out of retrieval data latched in the retrieval data register 12, i.e. the mask data register 13 masks a data portion not associated with retrieval.
The system decides a hit or miss by comparing the bit pattern of the retrieval data latched in the retrieval data register 12, which is not masked by the mask data latched in the mask data register 13, and the bit patterns of the data stored in the word memories 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n. A hit is determined when the bit pattern of the retrieval data matches a bit pattern stored in a word memory. The system outputs hit flag logic 1 to the hit lines corresponding to those word memories 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n that contain a "hit" bit pattern. The other hit lines remain at logic 0 designating a miss.
The CAM 10 has empty flag registers 15.sub.-- 1, 15.sub.-- 2, . . . , 15.sub.-- n, corresponding to the word memories 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n, which store an empty flag. The empty flag discriminates between logic 0, indicating valid retrieval data stored in those word memories and logic 1 indicating an empty status, i.e. that valid data is not stored in that word memory.
During the above mentioned retrieval, the system retrieves only those word memories with an empty flag in the empty flag registers 15.sub.-- 1, 15.sub.-- 2, . . . , 15.sub.-- n being logic 0 (indicating retrieval data is stored in the word memory).
The empty flags stored in the empty flag registers 15.sub.-- 1, 15.sub.-- 2, . . . , 15.sub.-- n are input to a priority encoder 17. The priority encoder 17 outputs, in a prescribed priority, the address data Highest Empty Address (HEA) which corresponds to the highest priority flag register (in this case, empty flag register 14.sub.-- n-1) out of empty flag registers in which a logic 1 empty flag is stored (in this case, empty flag registers 14.sub.-- n-1 and 14.sub.-- n). The address data HEA is always output irrespective of retrieval. To store new retrieval data in blank addresses of the CAM 10, the corresponding address data HEA must be referenced.
Like in retrieval, when storing data to the CAM 10, irrespective of whether the data is to be stored to blank addresses or not, the mask data stored in the mask data register 13 works effectively to overwrite only the data portions not masked by the mask data so that the masked data portions all remain unchanged.
The signals output to the hit lines 14.sub.-- 1, 14.sub.-- 2, . . . , 14.sub.-- n during the above mentioned retrieval operations are stored in the hit flag registers 16.sub.-- 1, 16.sub.-- 2, . . . , 16.sub.-- n respectively. Suppose here, as an example, that "0, 1, 1, 0, . . . , 0, 0" are stored in the hit flag registers 16.sub.-- 1, 16.sub.-- 2 , 16.sub.-- n respectively. In this case logic 0, indicating a miss, is stored in the hit flag registers corresponding to those empty flag registers in which empty flag logic 1. Indicating an empty word memory, is stored even if a bit pattern coincident with retrieval data is stored in the word memory.
Like empty flags, hit flags stored in the hit flag registers 16.sub.-- 1, 16.sub.-- 2, . . . , 16.sub.-- n are also input to the priority encoder 17. The priority encoder 17 outputs, in a prescribed priority order, the address data Highest Hit Address (HHA) which corresponds to the highest priority hit flag registers (in this case, hit flag registers 16.sub.-- 2 and 16.sub.-- 3) out of the hit flag registers in which hit flag logic 1 is stored. This example assumes that a smaller subscript register has a higher priority so that the memory address which corresponds to the hit flag register 16.sub.-- 2 is output.
The CAM 10 has a function to receive address signals in order to carry out read/write operations to designated addresses. When, for example, address data HHA is input from the priority encoder 17 into the address decoder 18 as address data AD, the address decoder 18 decodes this address data AD and outputs an access signal (logic 1 signal in this case) to one word line (in this case, word line 19.sub.-- 2). The access signal corresponds to the address data AD. For example, the data stored in the word memory 11.sub.-- 2 corresponding to the word line 19.sub.-- 2, to which an aaccess signal has been output, is read out to an output register 20.
The CAM 10 also has a function to erase the contents of all the word memories which have been hit by retrieval. Specifically, the content of the empty flag registers corresponding to all the word memories which have been hit by retrieval are replaced with logic 1 (blank status). This function is used, for example, to erase all lesser recent data of the data stored in the CAM 10 provided in, for example, a network frame switch, which will be described hereafter.
As mentioned above, the CAM 10 uses all or a prescribed portion of retrieval data to retrieve data stored in a number of word memories 11.sub.-- l, 11.sub.-- 2, . . . , 11.sub.-- n, in order to acquire the address HHA of the word memory that has coincident data. One of the main applications of such CAMs is a network frame switch which switchs the reception/transmission of network frames. The following will outline such a network frame switch.
Conventionally, in 9 network system, there has been employed a network frame switch, called a "hub," which switchs the transmission of network frames as an aggregate of information transferred over the network. FIG. 4 is a circuit block diagram of an exemplary configuration of a conventional network frame switch. The network fram switch 30, includes n number of port controllers 32.sub.-- 1, . . . , 32.sub.-- n connected to a bus 31, n number of ports 33.sub.-- 1, . . . , 33.sub.-- n corresponding to port controllers 32 1, . . . , 32.sub.-- n, LANs 34.sub.-- 1, . . . , 34.sub.-- n connected to the ports 33.sub.-- 1, . . . , 33.sub.-- n, and a plurality of terminals A, B, . . . C, . . . E, F, . . . G connected to LANs 34.sub.-- 1, . . . , 34.sub.-- n. Additionally, the bus 31 is provided with a CAM 35, a RAM 36, a CPU 37 and a packet memory 38.
The CAM 35, to which a retrieval function is added. is expensive in terms of the cost per bit and has a small memory capacity as compared to ordinary RAMs. To solve this problem, the network frame switch 30 uses the CAM 35 and the RAM 36 concurrently in such a way that only such data as directly required for retrieval is stored in the CAM 35. The data not directly associated with retrieval is stored in the RAM 36. The addresses of the word memories of the CAM 35 correspond to the addresses of the memory areas of the RAM 36 and are accessible via a signal line 39. The CAM 35 stores the address data of terminal addresses and the time stamp information, described hereafter. The RAM 36 stores the port numbers of ports connected with the terminals, the data of Virtual LAN (VLAN), and the other data referenced by the hardware of the network frame switch 30.
The CPU 37 has overall control of the network frame switch 30 while the packet memory 38 temporarily stores network frames which have been transmitted. The network frame switch 30 is usually provided with various other devices, which are not directly concerned here and. therefore, not shown nor described.
The operation of the conventional network frame switch 30 will now be described. Let us assume, for example, that a terminal B connected to the LAN 34.sub.-- 1 sends certain information having a network frame format to a terminal E connected to LAN 34.sub.-- n. In this example, the network frame has at its header, a record of the reception destination of the information, i.e., the destination address indicating terminal E, and the transmission source of the information, i.e., the source address indicating terminal B.
A network frame transmitted via port 33.sub.-- 1 from terminal B is first stored in the packet memory 38 via the port controller 32.sub.-- 1 and the bus 31. The CPU 37 extracts the destination address indicating a data transmission destination (terminal B in this example) from the header in the network frame and then sends it to the CAN 35. The CAM 35 has a record of the address data indicative of terminals A, B, . . . C, . . . , E, F, . . . G which constitute the network system. The RAN 36 stores the port numbers indicative of the connection destination of the terminals A, B, . . . C, . . . , Z, F, . . . G via parts 33.sub.-- 1, . . . , 33.sub.-- n.
Address data indicating the destination address is input to the CAM 35 and the address HHA of a word memory of the CAM 35, which stores the same address data as the input address data, is output. In response, the port number indicative of the terminal connection destination indicated by the destination address is read out based on the address corresponding to the address HHA of the RAM 36. Based on the part number read out, the CPU 37 recognizes this network frame as one to be transmitted to port 33.sub.-- n.
In this manner, when a port number is read out from the RAM 36, a network frame is subsequently input from the packet memory 38 via the bus 31 to the port controller 32.sub.-- n and then is sent via port 33.sub.-- n and LAN 34.sub.-- n to terminal E. Thus, a network frame switch effectively uses CAMs for speedy retrieval of addresses.
FIG. 5 shows data stored in the CAM 35 of the network frame switch 30 shown in FIG. 4. Each of the word memories 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n, stores the address data, indicative of the address of each terminal, and the time stamp information. As mentioned above, a destination address extracted from a network frame is used to carry out retrieval. From an address stored in RAM 36 corresponding to the address HHA obtained as a result of the retrieval, the port number to which the network frame is to be transmitted is determined.
Besides terminal address data, each word memory stores time stamp information. FIG. 6 shows an example of time stamp information. A prescribed time interval is considered to be one time slot so that p number of time slots are cycled one by one as time passes. To discriminate the p number of time slots from each other, their numbers, for example 1, 2, . . . , p, are called time stamp information.
When retrieval for CAM 35 is carried out based on a source address extracted from a network frame and, as a result, the same address as the source address is detected, time stamp information of the corresponding word memory is overwritten by the time stamp information indicating the time slot of that point in time. If, as a result of retrieval, the same address as the source address is not detected, data comprising that source address and time stamp information indicating a time slot of the current point in time is written into blank addresses. At the same time, the port number of a port to which a network frame having that source address has been transmitted is written into the RAM 36.
For each time interval, retrieval is carried out for CAM 35 using the time stamp information of the immediately previous time slot, If, as a result, the same time stamp information as that time stamp information of the previous time slot is detected, the data of the corresponding word memory is erased at that time. That is, as mentioned above, the contents of the empty flag register corresponding to that word memory are replaced by the contents that indicate emptiness. By erasing the address information of terminals which have not been concerned with communication for a long time, blank addresses in the CAM 35 can be used to for storage of new data.
In a network frame switch 30 having the above described configuration, the operations shown in FIG. 7 are carried out. FIG. 7 is a flowchart of the operations within a network frame switch such as shown in FIG. 4. FIG. 8 is a timing chart of the procedure.
In step 100, when a network frame is input from a port, a destination address DA indicative of a transmission destination is extracted from the network frame. Then, in stop S200, based on the destination address DA, retrieval is carried out. As a result, in step S300, an address HHA of a word memory which stores the same address as the destination address DA is output. Retrieval based on the destination address DA is abbreviated as SRCH.sub.-- DA here.
The address HHA obtained by SRCR.sub.-- DA is input to the RAM 36, thus reading out the port number of a destination port. In stop S400, after the address HHA is output, a source address SA, indicative of the transmission source address, is extracted from the network frame. The source address SA is then used by the CAM 35 in stop S500, to carry out retrieval.
Next, in stop S600, based on the retrieval results, it is decided whether the same address as the source address SA used in the retrieval, is already stored (i.e., hit) in the CAM 35. This decision is made in the CPU 37 in such a configuration as shown in FIG. 4. Retrieval based on the source address SA is abbreviated as SRCH.sub.-- SA here.
In stop S700, If a hit is recognized as a result of the decision, the hit address HHA is acquired and, in step S800, the time stamp information of the address HHA is overwritten by the time stamp information of the time slat of the current poaint in time. The overwriting of the time stamp information of the address HHA is abbreviated as STMP.sub.-- HHA. The time stamp information is thus overwritten to postpone the timing of erasing the information about a source address SA which belongs to a terminal, at the current point in time, which has participated in communication, from CAM 35.
On the other hand, if a miss is recognized in step S600, i.e. It is decided that the same address as a source address SA used in retrieval is not stored in CAM 35. In step S900, a top priority blank address (HEA) is acquired, so that in stop S1000, retrieval data (see FIG. 5) comprising the source address SA and the time stamp information of a time slot at the current point in time is stored in the address HEA for the next retrieval. The storing of retrieval data in the address HEA is abbreviated as STR.sub.-- HEA here. Accordlng to the STR.sub.-- HEA, the RAM 36 stores the port number of a port which has transmitted network frames having the source address SA.
To switch network frames speedily in this case, It is necessary to work out a method to speedily perform a series of processes such as described with reference to FIGS. 7 and 8. In other words, it is necessary to reduce the time required for each cycle shown in FIG. 8. One method for this purpose is to use a dedicated sequencer in place of the CPU 37 to perform the decision at step S600 or to employ a pipeline for a series of processes as described below.
FIG. 9 is a timing chart of a processing flow by a network frame switch when a pipeline system is employed. Although, as a result of pipelining, the CAM 35 can perform SRCH.sub.-- SA operations subsequent to the SRCH.sub.-- DA operations, time D required for acquiring the retrieval results cannot be reduced by pipelining because the time is limited by the retrieval speed of the CAM 35 Itself. Thus, in a series of cycles, overhead time takes a significant portion of the time that is required to decide STMP.sub.-- HHA or STR.sub.-- HEA. This problem prevents the processing from being performed more quickly.